package com.leetcode.partition4;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/11/16 12:07
 */
public class LC391完美矩形 {

    public static boolean isRectangleCover(int[][] rectangles) {
        return lineSweep(rectangles);
    }

    public static void main(String[] args) {
        int[][] rectangles = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}};
//        int[][] rectangles = {{1, 1, 3, 3}, {3, 1, 4, 2}, {1, 3, 2, 4}, {3, 2, 4, 4}};
        System.out.println(isRectangleCover(rectangles));
    }

    private static boolean lineSweep(int[][] rectangles) {
        int n = rectangles.length << 1, index = 0;
        //扫描线数组，四元组：[横坐标，纵坐标起点，纵坐标终点，左线段还是右线段]
        int[][] lines = new int[n][4];
        for (int[] rectangle : rectangles) {
            //加入四元组，1表示左线段，-1表示右线段
            lines[index++] = new int[]{rectangle[0], rectangle[1], rectangle[3], 1};
            lines[index++] = new int[]{rectangle[2], rectangle[1], rectangle[3], -1};
        }
        //对扫描线进行排序预处理，方便后续的线段判断
        Arrays.sort(lines, (o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]));
        // 一个完美矩形的充要条件为：对于完美矩形的每一条非边缘的竖边，都「成对」出现（存在两条完全相同的左边和右边重叠在一起）；
        // 对于完美矩形的两条边缘竖边，均独立为一条连续的（不重叠）的竖边。
        //分别存储相同横坐标下的 [左边线段] 和 [右边线段]，在对横坐标进行一次处理后，存放的应该是对应方向合并后的线段
        List<int[]> leftLine = new ArrayList<>(), rightLine = new ArrayList<>();
        //双指针遍历每一个集合中的横坐标，通过横坐标获取到矩形的纵线段
        for (int left = 0; left < n; ) {
            int right = left;
            leftLine.clear();
            rightLine.clear();
            //找到left横坐标相同的部分，使得区间[left, right)的横坐标都是相同的
            while (right < n && lines[left][0] == lines[right][0]) right++;
            //遍历这个区间内的线段（横坐标相同）
            for (int i = left; i < right; i++) {
                //得到当前横坐标上的线段，二元组 [纵坐标起始位置，纵坐标终止位置]
                int[] yLine = new int[]{lines[i][1], lines[i][2]};
                //引用传递，line直接指向左线段或者右线段集合
                List<int[]> line = lines[i][3] == 1 ? leftLine : rightLine;
                if (line.isEmpty()) line.add(yLine);
                else {
                    //如果能进来这个else，说明在当前横坐标上有多条“左边”或“右边”，将当前边和上一次的边取出对比，如果当前边的纵坐标起点和上一条边出现了交叉，必然不是完美矩阵
                    int[] prevYLine = line.get(line.size() - 1);
                    //线段有交叉，说明必然有交叉矩阵，不符合题意
                    if (yLine[0] < prevYLine[1]) return false;
                    else if (yLine[0] == prevYLine[1]) {
                        //如开始的x坐标是1，对应的线段是左线段[1,3]和[3,4]，当前线段和上一条线段能够刚好相接，直接修改上一条线段的纵坐标终止位置为当前线段的终止位置
                        prevYLine[1] = yLine[1];
                    } else {
                        line.add(yLine);
                    }
                }
            }
            if (left > 0 && right < n) {
                //若不是完美矩形的边缘竖边，检查放入的左线段和右线段，因为在上面的循环操作中，合法线段都最后合并成一条，所以还需要比较左线段和右线段对应的起始和终止点
                if (leftLine.size() != rightLine.size()) return false;
                for (int i = 0; i < leftLine.size(); i++) {
                    if (leftLine.get(i)[0] != rightLine.get(i)[0] || leftLine.get(i)[1] != rightLine.get(i)[1]) {
                        return false;
                    }
                }
                //左边缘竖边在经过合并后存放大小为1的线段数组，如x=1时，存放的是[1,4]，此时如果存在右边缘线段，必然不是完美矩形，反之亦然
            } else if (leftLine.size() + rightLine.size() != 1) return false;
            //移动left指针，继续寻找下一个x坐标对应的所有线段数组
            left = right;
        }
        return true;
    }

    private static boolean hashtable(int[][] rectangles) {
        //记录每个点出现的次数，如果面积相等且最终的大矩形4个点都出现1次，则返回true
        Map<Point, Integer> pointCount = new HashMap<>();
        //记录最后矩形的左下角和右上角位置
        Point leftBottom = new Point(rectangles[0][0], rectangles[0][1]), rightTop = new Point(rectangles[0][0], rectangles[0][1]);
        int areaSum = 0;
        for (int[] rectangle : rectangles) {
            int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
            //左下角要尽量小，右上角要尽量大，且每次遍历记录每个小矩形的面积
            leftBottom.x = Math.min(leftBottom.x, x1);
            leftBottom.y = Math.min(leftBottom.y, y1);
            rightTop.x = Math.max(rightTop.x, x2);
            rightTop.y = Math.max(rightTop.y, y2);

            //找出矩形的4个点
            Point p1 = new Point(x1, y1), p2 = new Point(x2, y1), p3 = new Point(x2, y2), p4 = new Point(x1, y2);
            pointCount.put(p1, pointCount.getOrDefault(p1, 0) + 1);
            pointCount.put(p2, pointCount.getOrDefault(p2, 0) + 1);
            pointCount.put(p3, pointCount.getOrDefault(p3, 0) + 1);
            pointCount.put(p4, pointCount.getOrDefault(p4, 0) + 1);
            areaSum += (x2 - x1) * (y2 - y1);
        }
        int x1 = leftBottom.x, y1 = leftBottom.y, x2 = rightTop.x, y2 = rightTop.y;
        Point p1 = new Point(x1, y1), p2 = new Point(x1, y2), p3 = new Point(x2, y1), p4 = new Point(x2, y2);
        if (areaSum != (rightTop.x - leftBottom.x) * (rightTop.y - leftBottom.y) || pointCount.getOrDefault(p1, 0) != 1
                || pointCount.getOrDefault(p2, 0) != 1 || pointCount.getOrDefault(p3, 0) != 1
                || pointCount.getOrDefault(p4, 0) != 1) {
            return false;
        }
        pointCount.remove(p1);
        pointCount.remove(p2);
        pointCount.remove(p3);
        pointCount.remove(p4);
        //其余点必须保证只出现两次或者四次
        for (Map.Entry<Point, Integer> entry : pointCount.entrySet()) {
            if (entry.getValue() != 2 && entry.getValue() != 4) return false;
        }
        return true;
    }

    private static class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() { return x + y; }
    }
}
